//
//  StringTest.swift
//  LeetCodeTest
//
//  Created by Clover on 2020/10/29.
//

import Foundation

public class StringDemo: NSObject{
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        if nums.count < 2 {
            return nums.count
        }
        var tagIndex = 0
        var tagValue = nums.first;
        
        for (_, value) in nums.enumerated() {
            if value != tagValue{
                tagIndex = tagIndex + 1;
                nums[tagIndex] = value
                tagValue = value;
            }
        }
        return tagIndex + 1;
    }
    
    func maxProfit(prices: [Int]) -> Int {
        var result = 0
        for i in 1..<prices.count{
            if prices[i] > prices[i-1] {
                result += (prices[i] - prices[i - 1])
            }
        }
        return result
    }

    func rotate(_ nums: inout [Int], _ k: Int) {
       // 暴力解法 - 最不推荐
//        for _ in 0..<k {
//            var previous = nums.last
//            for j in 0..<nums.count {
//                let temp = nums[j]
//                nums[j] = previous!
//                previous = temp
//            }
//            print(nums)
//        }
        
        // 2. 添加数组
        var tempArr = [Int](repeating: 0, count: nums.count)
        for i in 0..<nums.count {
            tempArr[(i + k) % nums.count] = nums[i]
        }
        print(tempArr)
        for i in 0..<nums.count {
            nums[i] = tempArr[i]
        }
        // 3、翻转数组
        // 4、连接法
    }
    
    // 重复元素
    func containsDuplicate(_ nums: [Int]) -> Bool {
        // 1.暴力破解
//        for (index, value) in nums.enumerated() {
//            for j in index + 1..<nums.count {
//                if nums[j] == value {
//                    return true
//                }
//            }
//        }
//        return false
        
        // 2.借助set
        var setValues = Set<Int>()
        for value in nums {
            if setValues.contains(value){
                return true
            }else{
                return setValues.insert(value).inserted
            }
        }
        return false
    }
    
//   136. 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    func singleNumber(_ nums: [Int]) -> Int {
          // 1.借助字典
//        var  tempDic = [Int : Int]()
//        for value in nums {
//            if var count = tempDic[value]{
//                count += 1
//                tempDic.updateValue(count, forKey: value)
//            }else{
//                tempDic.updateValue(1, forKey: value)
//            }
//        }
//        for (key,value) in tempDic {
//            if value == 1 {
//                return key
//            }
//        }
//        return 0;
        
        // 2. 借助set
//        var mySet = Set<Int>()
//        for value in nums {
//            if mySet.contains(value) {
//                mySet.remove(value)
//            }else{
//                mySet.insert(value)
//            }d
//        }
//        return mySet.first!
        
//        3.异或操作
        var singlevalue = 0
        for value in nums {
            singlevalue ^= value
        }
        return singlevalue
    }
//    66 : 加1
    func plusOne(_ digits: [Int]) -> [Int] {
    // 1. 转Int
//        for i in digits {
//
//        }
    // 2.数组尾部累加
        return [0]
    }

    //    20. 有效的括号
    func isValid(_ s: String) -> Bool {
        if s.count < 2 { return false }
        if s.count % 2 != 0 {return false}
        var stack = [String]()
        let sMap = ["(":")", "{":"}", "[":"]"]
        for char in s {
            if sMap.keys.contains(char.description) { // 左侧括号 入栈
                stack.append(char.description)
            }else if  char.description != stack.popLast() {// 右侧括号判断
                return false
            }
        }
        return stack.count == 0
    }

    //    67. 二进制求和
    func addBinary(_ a: String, _ b: String) -> String {
        return ""
    }
    
//    3. 无重复字符的最长子串
    func lengthOfLongestSubstring(_ s: String) -> Int {
        // 1.滑动数组
        var charArr = [Character]()
        var maxV = 0
        for char in s {
            if  charArr.contains(char){// 已存在 移除之前的数值
                let index = charArr.firstIndex(of: char)
                charArr.removeFirst(index! + 1)
            }
            charArr.append(char)
            if maxV < charArr.count {
                maxV = charArr.count
            }
        }
        return maxV
    }
    // 回文字
    func isPalindrome(_ s: String) -> Bool {
        //1.头尾指针
        var charArr = [Character]()
        for char in s.lowercased() {
            if (char >= "a" && char <= "z") || (char >= "0" && char <= "9") {
                charArr.append(char)
            }
        }
        var i = 0
        var j = charArr.count - 1
        while i < j {
            if charArr[i] != charArr[j] {
                return false
            }
            i = i + 1
            j = j - 1
        }
        return true
    }
    
    func longestPalindrome(_ s: String) -> String {
          // 1、暴力for + for 估计会超时
        if s.count <= 1 { return s }
        var maxStr = ""
        for i in 0..<s.count {
            for j in i..<s.count {
                let cutStr = cutOutString(str: s, range: i..<j+1)
                if isPalindrome(cutStr) && maxStr.count <= j - i {
                    maxStr = cutStr
                }
            }
            if maxStr.count > s.count - i - 1 {
                return maxStr
            }
        }
        return maxStr
    }
    
    func cutOutString(str:String, range:Range<Int>) -> String
    {
        if range.lowerBound < 0 || range.upperBound > str.count || str.count == 0
        {
            return ""
        }
        let start_index = str.index(str.startIndex, offsetBy: range.lowerBound)
        let end_index = str.index(str.startIndex, offsetBy: range.upperBound)
            
        return String(str[start_index..<end_index])
    }
}

class ListObjc {
    var finalArr = [Int]()
    
    public class ListNode {
        public var val: Int
        public var next: ListNode?
        public init() { self.val = 0; self.next = nil; }
        public init(_ val: Int) { self.val = val; self.next = nil; }
        public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
    }
    
    func reversePrint(_ head: ListNode?) -> [Int] {
        // 1. 插入法
    //         var tagNode = head
    //         var returnArr = [Int]()
    //         while (tagNode != nil) {
    //             returnArr.append(tagNode!.val) // 20ms
    // //          returnArr.insert(tagNode!.val, at: 0) 48ms
    //             tagNode = tagNode?.next
    //         }
    //         return returnArr.reversed()
        //  2. 递归法
        if head == nil {
            return []
        }
        reversePrint(head!.next)
        finalArr.append(head!.val)
        return finalArr
    }
    
    func deleteNode(_ node: ListNode?) {
        node?.val = node?.next?.val ?? 0
        node?.next = node?.next?.next
    }
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        //1. 2次扫描
        //        var nodeCount = 1
        //        var tagNode = head
        //        while tagNode?.next != nil {
        //            nodeCount += 1
        //            tagNode = tagNode?.next
        //        }
        //
        //        var finalTag = head
        //        for _ in 0..<nodeCount - n{
        //            finalTag = finalTag?.next
        //        }
        //        if let value = finalTag?.next?.val {
        //            finalTag?.val = value
        //        }
        //        finalTag?.next = finalTag?.next?.next
        //        return head
        
        let dummy = ListNode(0)
        dummy.next = head
        var fastNode: ListNode? = dummy
        var slowNode: ListNode? = dummy
        
        for _ in 1...n+1 {
            // 快指针先走n+1步
            fastNode = fastNode?.next
        }
        
        while fastNode != nil {
            slowNode = slowNode?.next
            fastNode = fastNode?.next
        }
        
        slowNode?.next = slowNode?.next?.next
        
        return dummy.next
    }
    
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var curr = head
        while curr != nil {
            let nextTemp = curr?.next
            curr?.next = prev
            prev = curr
            curr = nextTemp
        }
        return prev
    }
//    2. 两数相加
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        //1.指向
        let preHader = ListNode(0)
        var preNode = preHader
        var newl1 = l1
        var newl2 = l2
        while (newl1 != nil && newl2 != nil) {
            if newl1!.val <= newl2!.val {
                preNode.next = newl1
                newl1 = newl1?.next
            }else{
                preNode.next = newl2
                newl2 = newl2?.next
            }
            preNode = preNode.next!
        }
        preNode.next = newl1 == nil ? newl2 : newl1
        return preHader.next
        //2.递归
    }
    
    func isPalindrome(_ head: ListNode?) -> Bool {
        //1、头尾指针 思路>转换为arr 头尾比较
        var nodeArr = [Int]()
        var tagNode = head
        while tagNode != nil {
            nodeArr.append(tagNode!.val)
            tagNode = tagNode?.next
        }
        var i = 0
        var j = nodeArr.count - 1
        while i < j {
            if nodeArr[i] != nodeArr[j] {
                return false
            }
            i += 1
            j -= 1
        }
        return true
    }
    
    // 是否有环
    func hasCycle(_ head: ListNode?) -> Bool {
        var fastNode = head?.next
        var lowNode = head
        while lowNode != nil && fastNode != nil {
            if fastNode === lowNode {
                return true
            }
            fastNode = fastNode?.next?.next
            lowNode = lowNode?.next
        }
        return false
    }
    
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1Node = l1
        var l2Node = l2
        var l3Node = ListNode.init()
        let dummyNode = l3Node
        
        var needAdd = 0
        while l1Node != nil || l2Node != nil {
            var addval = (l1Node?.val ?? 0) + (l2Node?.val ?? 0) + needAdd
            if addval >= 10 {
                needAdd = 1
                addval = addval % 10
            }else{
                needAdd = 0
            }
            let newNode = ListNode(addval)
            l3Node.next = newNode
            l3Node = newNode
            
            l1Node = l1Node?.next
            l2Node = l2Node?.next
        }
        if needAdd != 0 {
            let lastNode = ListNode(needAdd)
            l3Node.next = lastNode
        }
        
        return dummyNode.next
    }
    // 328. 奇偶链表
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        let B_head = head?.next
        var now_node = head
        var A_node = head
        var count = 1
        while now_node != nil {
            let tempNode = now_node?.next
            now_node?.next = now_node?.next?.next
            if count % 2 != 0 && now_node?.next != nil {// 奇数
                A_node = now_node?.next
            }
            count += 1
            now_node = tempNode;
        }
        A_node?.next = B_head
        return head
    }
}

class Solution {
    
    func reverseLeftWords(_ s: String, _ n: Int) -> String {
//        let tagIndex = s.index(s.startIndex, offsetBy: n)
//        let topStr  = s.prefix(upTo: tagIndex)
//        let endStr  = s.suffix(from: tagIndex)
//        let returnStr = endStr + topStr
//        return String(returnStr)
        
        return String(s[s.index(s.startIndex, offsetBy: n)..<s.endIndex]) + s[s.startIndex..<s.index(s.startIndex, offsetBy: n)]
    }
    
//    239 滑动窗口的最大值
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        if k == 0 {
            return []
        }
        var finalArr = [Int]()
        var topIndex = 0
        var endIndex = k - 1
        while endIndex <= nums.count - 1 {
            var max = nums[topIndex]
            for i in topIndex...endIndex {
                if max < nums[i] {
                    max = nums[i]
                }
            }
            finalArr.append(max)
            topIndex += 1
            endIndex += 1
        }
        return finalArr
    }
    
//    509  斐波那契数列
    func fib(_ n: Int) -> Int {
        //        if n == 0 {return 0}
        //        if n == 1 {return 1}
        //        return (fib(n - 1) + fib(n - 2)) % 1000000007
        if n < 2{
            return n
        }
        var first = 0
        var second = 1
        for _ in 1..<n{
           let sum = (first + second) %  1000000007
            first = second
            second = sum
        }
        return second
    }
    
    func reverse(_ x: Int) -> Int {
        var numStr = ""
        var boolTag = false
        if x > 0 {
            numStr = String.init(format: "%d", arguments: [x])
        }else{
            boolTag = true
            numStr = String.init(format: "%d", arguments: [-x])
        }

        return 0
//        if boolTag {
//            return Int.init(returnStr)!
//        }
//        return Int.init(returnStr)!
    }
    
//    字符串中的第一个唯一字符
    func firstUniqChar(_ s: String) -> Int {
        var hashMap = [String.Element : Int]()
        for char in s {
            if let count = hashMap[char] {
                hashMap[char] = count + 1
            }else{
                hashMap .updateValue(1, forKey: char)
            }
        }
        for (index, char) in s.enumerated() {
            if  hashMap[char] == 1 {
                return index
            }
        }
        return -1
    }
    
//    有效的字母异位词
    func isAnagram(_ s: String, _ t: String) -> Bool {
        return s.sorted() == t.sorted()
    }
    
    
    func isPalindromeS(_ x: Int) -> Bool {
            //1,头尾指针
        if x < 0 { return false}
        var str = String(x)
        var charArr = [Character]()
        for char in str {
            charArr.append(char)
        }
        var left = 0
        var right = charArr.count - 1
        while left < right {
            if charArr[left] != charArr[right] {
                return false
            }
        }
        return true
    }
    func myAtoi(_ s: String) -> Int {
        return 0
    }
    
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if needle.count == 0  {
            return 0
        }
        guard haystack.contains(needle) else {
            return -1
        }
        // 存在
        let range = haystack.range(of: needle)
        range?.isEmpty
        return 0
    }
    
    func maxProfit(_ prices: [Int]) -> Int {
            // 1.计算差值
        var minValue = Int.max
        var sumValue = 0
        for i in 0..<prices.count {
            if prices[i] < minValue {
                minValue = prices[i]
            }else if(prices[i] - minValue > sumValue){
                sumValue = prices[i] - minValue
            }
        }
        return sumValue
    }
    
//    53. 最大子序和
    func maxSubArray(_ nums: [Int]) -> Int {
        var pre = 0
        var maxAns = nums[0];
        for x in nums {
            pre = max(pre + x, x)
            maxAns = max(maxAns, pre)
        }
        return maxAns;
    }
//    打家劫舍
    func rob(_ nums: [Int]) -> Int {
        var tounum = 0
        var butouNum = 0
        for i in 0..<nums.count {
//            tounum =
        }
       return 0
    }
    
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.isEmpty { return []}
        var numDic = [Int: Int]()
        for i in 0..<nums.count {
            if numDic.keys.contains(nums[i]){
                return [numDic[nums[i]]!, i]
            }else{
                numDic.updateValue(i, forKey: target - nums[i])
            }
        }
        return []
    }
    
//    941. 有效的山脉数组
    func validMountainArray(_ A: [Int]) -> Bool {
        let N = A.count
        var i = 0
        // 上山
        while i + 1 < N && A[i] < A[i + 1] {
            i += 1
        }
        // 山顶判断
        if i == N - 1 || i == 0  {
            return false
        }
        // 下山
        while i + 1 < N && A[i] > A[i + 1] {
            i += 1
        }
        // 终点核对
        return i == N - 1
    }
//    LCP 18. 早餐组合
    func breakfastNumber(_ staple: [Int], _ drinks: [Int], _ x: Int) -> Int {
//         1.for + for 超时
        var count = 0
        for stapleV in staple {
            if stapleV >= x {
                continue
            }

            for dirnkV in drinks {
                if dirnkV >= x {continue}
                if stapleV + dirnkV <= x {
                    count += 1
                }
            }
        }
        return count % 1000000007
    }
//    57. 插入区间
    func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
        var left = newInterval[0]
        var right = newInterval[1]
        var placed = false
        var ansList = [[Int]]()
        for interval in intervals {
            if interval[0] > right { // 右侧
                if !placed {
                    ansList.append([left, right])
                    placed = true
                }
                ansList.append(interval)
            }else if interval[1] < left{ // 左侧
                ansList.append(interval)
            }else{ // 有交集
                left = min(interval[0], left)
                right = max(interval[1], right)
            }
        }
        if !placed {
            ansList.append([left, right])
        }
        return ansList
    }
//    4. 寻找两个正序数组的中位数
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        // 1、 暴力方式
        var newArr = [Int]()
        newArr.append(contentsOf: nums1)
        newArr.append(contentsOf: nums2)
        newArr.sort()
        var value = 0.0
        let centerCount = newArr.count / 2
        if newArr.count % 2 == 0 {
            value = Double(newArr[centerCount - 1] + newArr[centerCount]) / 2.0
        }else{
            value = Double(newArr[centerCount])
        }
        return value
    }

    //    1356. 根据数字二进制下 1 的数目排序
    func sortByBits(_ arr: [Int]) -> [Int] {
        var sortArr = arr
        sortArr.sort { (x, y) -> Bool in
            if x.nonzeroBitCount != y.nonzeroBitCount {
                return x.nonzeroBitCount < y.nonzeroBitCount
            }
            return x < y
        }
        return sortArr
    }
    
    // 922. 按奇偶排序数组 II
    func sortArrayByParityII(_ A: [Int]) -> [Int] {
        var singleArr = [Int]()
        var doubleArr = [Int]()
        var finalArr  = [Int]()
        for value in A {
            if value % 2 == 0 {
                doubleArr.append(value)
            }else{
                singleArr.append(value)
            }
        }
        
        for i in 0..<A.count {
            if i % 2 == 0 {
                finalArr.append(doubleArr.last!)
                doubleArr.removeLast()
            }else{
                finalArr.append(singleArr.last!)
                singleArr.removeLast()
            }
        }
        return finalArr;
        
        //2、单次交换
//        for
    }
}



class TreeMapObj{
    public class TreeNode {
        public var val: Int
        public var left: TreeNode?
        public var right: TreeNode?
        public init(_ val: Int) {
            self.val = val
            self.left = nil
            self.right = nil
        }
    }
    
    func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }else{
            let leftH = maxDepth(root?.left)
            let rightH = maxDepth(root?.right)
            return max(leftH,rightH) + 1
        }
    }
    
    func isValidBST(_ root: TreeNode?) -> Bool {
        isValidHelp(root, nil, nil)
    }
    
    func isValidHelp(_ root: TreeNode?, _ lower: Int?, _ upper: Int?) -> Bool {
        if root == nil {
            return true
        }
        let val = root!.val
        if lower != nil && val <= lower! {
            return false
        }
        if upper != nil && val >= upper! {
            return false
        }
        
        if !isValidHelp(root?.right, val, upper) {
            return false
        }
        
        if !isValidHelp(root?.left, lower, val) {
            return false
        }
        
        return true
    }
}

class searchObj{
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
           // 1.遍历插入
        var newNums = [Int]()
        for i in 0..<m {
            newNums.append(nums1[i])
        }
        newNums.append(contentsOf: nums2)
        newNums.sort()
        nums1 = newNums
    }
}

struct personB {
    var name: String = ""
}

struct personA {
    var name: String = ""
}
